﻿namespace AdvancedTraining.Lesson50;

/// <summary>
/// 安装栅栏问题 - LeetCode 587
/// 使用Andrew算法计算凸包，找到能够包围所有点的最小多边形
/// </summary>
public class ErectTheFence //leetcode_0587
{
    /// <summary>
    /// 计算能够包围所有点的最小凸包
    /// 算法思路：Andrew算法
    /// 1. 将点按x坐标排序，x相同时按y坐标排序
    /// 2. 从左到右构建下凸包
    /// 3. 从右到左构建上凸包
    /// 4. 合并结果并去重
    /// 时间复杂度：O(n log n)，主要用于排序
    /// 空间复杂度：O(n)，用于存储栈和排序结果
    /// </summary>
    /// <param name="points">二维点数组</param>
    /// <returns>构成凸包的点数组</returns>
    public static int[][] OuterTrees(int[][] points)
    {
        int n = points.Length;
        if (n <= 1) return points;

        int s = 0;
        var stack = new int[n << 1][];

        // 将点按照x坐标排序（如果x相同则按y排序）
        var sortedPoints = points.OrderBy(p => p[0]).ThenBy(p => p[1]).ToArray();

        // 第一次遍历，从左到右构建下凸包
        for (int i = 0; i < n; i++)
        {
            while (s > 1 && Cross(stack[s - 2], stack[s - 1], sortedPoints[i]) > 0)
            {
                s--;
            }
            stack[s++] = sortedPoints[i];
        }

        // 第二次遍历，从右到左构建上凸包
        for (int i = n - 2; i >= 0; i--)
        {
            while (s > 1 && Cross(stack[s - 2], stack[s - 1], sortedPoints[i]) > 0)
            {
                s--;
            }
            stack[s++] = sortedPoints[i];
        }

        // 去重：按降序排序，移除重复点
        var result = new List<int[]>();
        var comparer = Comparer<int[]>.Create((a, b) => b[0] == a[0] ? b[1] - a[1] : b[0] - a[0]);
        Array.Sort(stack, 0, s, comparer);
        result.Add(stack[0]);

        for (int i = 1; i < s; i++)
        {
            // 如果当前点与前一个点位置不同，则添加到结果中
            if (stack[i][0] != stack[i - 1][0] || stack[i][1] != stack[i - 1][1])
            {
                result.Add(stack[i]);
            }
        }

        return result.ToArray();
    }

    /// <summary>
    /// 叉乘计算
    /// 假设有a、b、c三个点，计算从a到c的向量相对于从a到b的向量的位置
    /// 如果返回正数：a到c的向量在a到b的向量右侧
    /// 如果返回负数：a到c的向量在a到b的向量左侧
    /// 如果返回0：两个向量重合
    /// </summary>
    /// <param name="a">起始点</param>
    /// <param name="b">中间点</param>
    /// <param name="c">终点</param>
    /// <returns>叉乘结果</returns>
    public static int Cross(int[] a, int[] b, int[] c)
    {
        return (b[1] - a[1]) * (c[0] - b[0]) - (b[0] - a[0]) * (c[1] - b[1]);
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 安装栅栏问题测试 ===");

        // 测试用例1: LeetCode官方示例
        Test1();

        // 测试用例2: 正方形
        Test2();

        // 测试用例3: 线性排列的点
        Test3();

        // 测试用例4: 单个点
        Test4();

        // 测试用例5: 重复点
        Test5();

        // 测试用例6: 三角形
        Test6();

        // 测试用例7: 复杂形状
        Test7();

        Console.WriteLine("\n=== 算法说明 ===");
        Console.WriteLine("凸包算法：使用Andrew算法计算最小凸多边形");
        Console.WriteLine("核心思想：维护一个单调栈，确保相邻三点总是左转");
        Console.WriteLine("叉乘意义：判断三点间的转向关系");
        Console.WriteLine("时间复杂度：O(n log n) - 主要用于排序");
        Console.WriteLine("空间复杂度：O(n) - 存储栈和排序结果");
    }

    /// <summary>
    /// 测试用例1: LeetCode官方示例
    /// </summary>
    private static void Test1()
    {
        Console.WriteLine("\n测试用例1: LeetCode官方示例");
        int[][] points = [[0, 0], [2, 2], [1, 0], [0, 4], [3, 3], [2, 4]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例2: 正方形
    /// </summary>
    private static void Test2()
    {
        Console.WriteLine("\n测试用例2: 正方形");
        int[][] points = [[0, 0], [1, 0], [1, 1], [0, 1]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例3: 线性排列的点
    /// </summary>
    private static void Test3()
    {
        Console.WriteLine("\n测试用例3: 线性排列的点");
        int[][] points = [[0, 0], [1, 1], [2, 2], [3, 3]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例4: 单个点
    /// </summary>
    private static void Test4()
    {
        Console.WriteLine("\n测试用例4: 单个点");
        int[][] points = [[0, 0]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例5: 重复点
    /// </summary>
    private static void Test5()
    {
        Console.WriteLine("\n测试用例5: 重复点");
        int[][] points = [[0, 0], [0, 0], [1, 1], [1, 1]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例6: 三角形
    /// </summary>
    private static void Test6()
    {
        Console.WriteLine("\n测试用例6: 三角形");
        int[][] points = [[0, 0], [2, 0], [1, 2]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }

    /// <summary>
    /// 测试用例7: 复杂形状
    /// </summary>
    private static void Test7()
    {
        Console.WriteLine("\n测试用例7: 复杂形状");
        int[][] points = [[0, 2], [1, 1], [2, 2], [2, 0], [4, 0], [4, 2], [3, 3], [1, 3]];
        var result = OuterTrees(points);
        Console.WriteLine($"输入: [{string.Join(", ", points.Select(p => $"[{p[0]},{p[1]}]"))}]");
        Console.WriteLine($"输出: [{string.Join(", ", result.Select(p => $"[{p[0]},{p[1]}]"))}]");
    }
}